// https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487246&idx=1&sn=4a514020ce9dc8777e2d1d503188b62b&chksm=9bd7f106aca078108102fe76799983ee8ea3bd759508e6dbfe87bc9da6edbeb8b8dd73deb0d7&scene=178&cur_album_id=1318896187793260544#rd

// 输入一个字符串，其中包含[](){}六种括号，请你判断这个字符串组成的括号是否合法

// 遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配

class Test {
    public bool isValid(string str) {
        stack<char> left;
        for (char c : str) {
            if (c == '(' || c == '{' || c == '[')
                left.push(c);
            else { // 字符 c 是右括号
                if (!left.empty() && leftOf(c) == left.top())
                    left.pop();
                else
                    // 和最近的左括号不匹配
                    return false;
            }
        }
        // 是否所有的左括号都被匹配了
        return left.empty();
    }

    public char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ')') return '(';
        return '[';
    }
}